package com.zdp.leetcodeMiddle;

import java.util.HashMap;
import java.util.Map;

public class 最佳直线 {
    public static void main(String[] args) {
       最佳直线 demo = new 最佳直线();
       int[][] a = {{0,0},{1,1},{1,0},{2,0},{3,0}};
        int[] ints = demo.bestLine(a);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    /*
    * 题目描述：
    * 给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。
    设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案
    * ，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。
    示例：
    输入： [[0,0],[1,1],[1,0],[2,0]]
    输出： [0,2]
    解释： 所求直线穿过的3个点的编号为[0,2,3]
    提示：
    2 <= len(Points) <= 300
    len(Points[i]) = 2
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/best-line-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
        * */

    /*
        解题思路：
    * 计算每一对点所在的直线，将直线存入Map中
    * 如何标识直线？ ===> 使用直线的斜率 来代表一条直线
    * 当点在同一条直线上时，该记录经过的点数+1 ---> 该方法只能比较大小，不能精确计算该直线经过了几个点，因为点会重复（感觉这边可以优化？）
    * */
    public int[] bestLine(int[][] points) {
        Map<String,Integer>map = new HashMap<>();
        Map<String,int[]>record = new HashMap<>();
        long A, B, C;
        int max = 0;
        String maxKey = "";
        for(int i=0;i<points.length;i++){
            for(int j=i+1;j<points.length;j++){
                A = points[j][1]-points[i][1]; //y2-y1
                B = points[i][0]-points[j][0];// x1 -x2
                C = ((long)points[j][0])*points[i][1] - ( (long) points[i][0] )*points[j][1];
                //求最大公约数
                long t = gcd(A,gcd(B,C));
                A /=t;
                B /=t;
                C /=t;
                String key = ""+A+","+B+","+C;
                int count = map.getOrDefault(key,0)+1;
                map.put(key,count);
                if(count==1){
                    //说明是该直线是第一次出现，记录其最前的两个点
                    record.put(key,new int[]{i,j});
                }
                if(count>max){
                    max = count;
                    maxKey = key;
                }else if(count==max){
                    //如果相等，找较小的点
                    int[] maxNum = record.get(maxKey);
                    int[] nowNum = record.get(key);
                    if(maxNum[0]>nowNum[0] || (maxNum[0]==nowNum[0]&&maxNum[1]>nowNum[1])){
                        max = count;
                        maxKey = key;
                    }
                }
            }
        }
        //System.out.println(max);
        return record.get(maxKey);
    }

    //求最大公约数
    //辗转相除法，两数相除，除数做被除数，余数做除数，直到余数==0
    long gcd(long a,long b){
        return b==0?a:gcd(b,a%b);
    }
}
